using System;
using System.Text;

namespace ParserGenerator.CharacterMapping
{
    [Serializable]
    internal sealed class CharMapChain
    {
        public CharMapLink First { get; }

        public CharMapChain(CharClass value)
        {
            if (value == null)
                throw new ArgumentNullException(nameof(value));
            for (int i = value.Intervals.Count - 1; i >= 0; i--)
            {
                CharInterval item = value.Intervals[i];
                CharMapLink link = new CharMapLink(item);
                link.Next = First;
                if (First != null)
                    First.Previous = link;
                First = link;
            }
        }

        public void Disjoint(CharMapConstructor map)
        {
            if (map == null)
                throw new ArgumentNullException(nameof(map));
            for (CharMapLink m = First; m != null; m = m.Next)
            {
                CharMapLink n = map.Find(m.First);

                // Check tail
                if (n.Last < m.Last)
                {
                    // Split link in chain
                    CharMapLink link = new CharMapLink(n.Last + 1, m.Last);
                    m.Last = n.Last;
                    link.AddAfter(m);
                }
                else if (m.Last < n.Last)
                {
                    // Split link in tree
                    CharMapLink link = new CharMapLink(m.Last + 1, n.Last);
                    n.Last = m.Last;
                    link.AddAfter(n);
                    map.Insert(link);
                }

                // Check head
                if (n.First < m.First)
                {
                    // Split link in tree (at head)
                    CharMapLink link = new CharMapLink(m.First, n.Last);
                    n.Last = m.First - 1;
                    link.AddAfter(n);
                    map.Insert(link);
                }
            }
        }

        public void Partition(CharMapConstructor map)
        {
            if (map == null)
                throw new ArgumentNullException(nameof(map));
            for (CharMapLink p = First; p != null; p = p.Next)
            {
                // Search tree
                CharMapLink head = map.Find(p.First);
                CharMapLink newEC = head;
                CharMapLink oldEC = head.Previous;
                if (oldEC != null)
                {
                    head.Previous = null;
                    map.AddHead(head);
                }

                // Compare links in chain and tree
                CharMapLink m = p.Next;
                CharMapLink n = head.Next;
                while (m != null && n != null)
                {
                    if (m.Last < n.First)
                    {
                        // Skip link in chain; process it later
                        m = m.Next;
                    }
                    else if (n.Last < m.First)
                    {
                        // Leave link in old equivalence class
                        n.Previous = oldEC;
                        if (oldEC != null)
                            oldEC.Next = n;
                        else
                            map.AddHead(n);
                        oldEC = n;
                        n = n.Next;
                    }
                    else
                    {
                        // Move link to new equivalence class
                        n.Previous = newEC;
                        newEC.Next = n;
                        newEC = n;
                        n = n.Next;

                        // Pop link from chain
                        // NOTE: This modifies the chain, that's why it should not be cached.
                        m.Pop();
                        m = m.Next;
                    }
                }

                // Terminate old and new equivalence classes
                if (n != null)
                    n.Previous = oldEC;
                if (oldEC != null)
                    oldEC.Next = n;
                else if (n != null)
                    map.AddHead(n);
                newEC.Next = null;
            }
        }

        public sealed override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append("[");
            for (CharMapLink n = First; n != null; n = n.Next)
            {
                if (sb.Length > 1)
                    sb.Append(", ");
                sb.Append(n);
            }
            sb.Append("]");
            return sb.ToString();
        }
    }
}
